/**
 * 
 */
package tree;

/**
 * @author xyyi
 *
 */
public class CompleteBSTNodeNumber {

	public int totalCompleteBSTNumber(Node<Integer> root) {
		int total = 0;

		int height = getRightHeight(root);
		while (height > 0 && root != null) {
			if (this.getRightHeight(root.left) == height - 1) {
				total += this.calcFullBSTNodNumber(height - 1);
				root = root.right;
			} else {
				total += this.calcFullBSTNodNumber(height - 2);
				root = root.left;
			}
		}

		return total;
	}

	private int getRightHeight(Node<Integer> root) {
		int height = 0;
		if (root == null)
			return height;

		while (root != null) {
			height++;
			root = root.right;
		}

		return height;
	}

	private int getLeftHeight(Node<Integer> root) {
		int height = 0;
		if (root == null)
			return height;

		while (root != null) {
			height++;
			root = root.left;
		}

		return height;
	}

	private int calcFullBSTNodNumber(int height) {
		return (int) Math.pow(2, height) - 1;
	}

	/**
	 * 
	 */
	public CompleteBSTNodeNumber() {
		// TODO Auto-generated constructor stub
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}
